377. Combination Sum IV

Medium

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

最近在刷动态规划的题，这篇文章是我写的动态规划一点想法，和大家分享一下

1.dp

动态规划，dp list是一个（0，target）不断增加的一维矩阵。举例子，nums = [1, 2, 3], target = 5，当amount = 1时只能使用nums里的），当amount = 2时，除了使用nums里的2，还能使用在可以构成amount = 1的情况（也就是1），因为只需在此基础上加nums里的1就可以构成2了，所以dp[2] = 2（0+1+1）。当amount = 3时，除了使用nums里的3，还能使用amount = 2，和amount = 1的情况，dp[3] = 0 + 1(自身) + 1（和为1的组合数） + 2（和为2的组合数） = 4，然后以此类推。

⚠️edge case: 当target = 0时，不加任何数也是一种组合。但没有nums时，没有任何方法可以达到target。这种edge case在换硬币的题里也出现过。

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        if not target: return 1
        if not nums: return 0
        
        dp = [1] + [0] * target
        for i in range(target+1):
            for num in nums:
                if i-num < 0: continue
                elif i-num == 0: dp[i] += dp[0]
                else: dp[i] += dp[i-num]

        return dp[-1]

改良版：

当nums是从小到大排列的，当一个数使得i-num小于0时，后面的num只会更大，所以可以直接break

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        if not target: return 1
        if not nums: return 0
        nums = sorted(nums)
        dp = [1] + [0] * target
        for i in range(target+1):
            for num in nums:
                if i-num < 0: break
                else: dp[i] += dp[i-num]
        return dp[-1]

速度虽然快了，但time complexity 还是O(n*m), n is the length of nums, m is target. Space complexity is O(m)